package com.leetcode.partition9;

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2022/2/4 10:11
 */
public class LC882细分图中的可到达结点 {

    private static final int N = 3010, M = (int) 2e4, P = 13331;
    private static int[] h = new int[N], e = new int[M], w = new int[M], ne = new int[M];
    private static boolean[] st = new boolean[N];
    private static int[] dist = new int[N];

    private static PriorityQueue<int[]> heap = new PriorityQueue<>(N, (o1, o2) -> Integer.compare(o1[1], o2[1]));
    private static Map<Integer, Integer> used = new HashMap<>(M);
    private static int[][] edges;

    private static int n = 0, m = 0, idx = 1;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        int n = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]), maxMoves = Integer.parseInt(ss[2]);
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            ss = reader.readLine().split(" ");
            int a = Integer.parseInt(ss[0]), b = Integer.parseInt(ss[1]), c = Integer.parseInt(ss[2]);
            edges[i] = new int[]{a, b, c};
        }
        writer.write(reachableNodes(edges, maxMoves, n) + "\n");
        writer.flush();
    }

    public static int reachableNodes(int[][] _edges, int maxMoves, int _n) {
        n = _n;
        m = _edges.length * 2;
        edges = _edges;
        for (int[] edge : _edges) {
            int a = edge[0], b = edge[1], c = edge[2];
            add(a, b, c);
            add(b, a, c);
        }
        return dijkstra(maxMoves);
    }

    private static int dijkstra(int maxMoves) {
        int ans = 0;
        for (int i = 0; i <= n; i++) dist[i] = maxMoves + 1;
        heap.add(new int[]{0, 0});
        dist[0] = 0;
        while (!heap.isEmpty()) {
            int[] cur = heap.poll();
            int u = cur[0], d = cur[1];
            if (st[u]) continue;
            st[u] = true;
            ans++;
            for (int i = h[u]; i != 0; i = ne[i]) {
                int v = e[i], hash = hash(u, v), nd = d + w[i] + 1;
                used.put(hash, Math.min(w[i], maxMoves - d));
                if (dist[v] > nd) {
                    dist[v] = nd;
                    heap.add(new int[]{v, dist[v]});
                }
            }
        }
        //加上所有边的使用情况
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            int u1 = used.getOrDefault(hash(u, v), 0), u2 = used.getOrDefault(hash(v, u), 0);
            ans += Math.min(w, u1 + u2);
        }
        return ans;
    }

    private static int hash(int a, int b) {
        return a * P + b;
    }

    private static void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx;
        w[idx++] = c;
    }
}
